#include<stdio.h>
#include<stdlib.h>
#include<string.h> 

#ifndef __GHASH_H_
#define __GHASH_H_

#define D_HASHSIZE 512
typedef struct ST_Node
{
   char * key;
   char * value;
   struct ST_Node * next;
} Node;



void HashInit();
Node *  HashInsert(char * key, char * value);
int  HashRemove(char * key);
Node *  HashSearch(char * key);
void FreeGHash();
void HashTraversal();

#endif
 


static Node* hashtab[D_HASHSIZE];
 

void HashInit()
{
 	 int i=0;
 	 for(i=0; i<D_HASHSIZE; i++)
 	 {
	  	hashtab[i]=NULL;
     }
}

Node *  HashInsert(char * key,char * value)
{
 	 Node * np;
 	 unsigned int hashval;
 	 if((np=HashSearch(key))==NULL) /*如果没有相同的key则直接插入*/
 	 {
         np=(Node *)malloc(sizeof(Node));
         if(NULL==np || NULL ==(np->key = strdup(key))  	 /*strdup:复制一个字符串副本*/
					 || NULL ==(np->value = strdup(value)) 
		   )
         {
             return NULL;
         }
         hashval = _Hash(key);
         np->next = (Node *)hashtab[hashval]; /*解决不同的key算出相同hash值的collision*/
         hashtab[hashval] = np;
     }
     else	/*如果有则覆盖*/
     {
	  	 free(np->value); 
	  	 if((np->value=strdup(value))== NULL)
	  	 {
		    return NULL;
         }
 	 }
 	 return np;
}


int  HashRemove(char * key)
{
	Node * np = NULL;
	np = HashSearch(key);
    if(np == (Node *)hashtab[_Hash(key)]) /*如果是数组所指向的链表的头指针则让数组指向next*/
    {
        freeNode(np);
        hashtab[_Hash(key)] = np->next;
    }

	  
	return 0; /*正常返回0*/
}

/*
	确保_Hash(key) 值相同
	&& key字符串也相同
	return: 所定位的指针
*/
Node *  HashSearch(char * key)
{
    Node  *np;

    for(np = (Node *)hashtab[_Hash(key)]; /*定位HashTable所指向的链表 进行循环比较*/
        np != NULL;
        np = np->next)
      if(strcmp(key, np->key) == 0) 
           return np;
    return NULL;
}

void FreeGHash()
{ 
 	 for(int i=0; i<D_HASHSIZE; i++)
 	 {
	     if(hashtab[i]!=NULL)
	     {
		    Node * tmp;
		    Node * deln;
		    for(tmp=hashtab[i]; tmp!=NULL; tmp=hashtab[i])
		    {
			     hashtab[i]=tmp->next;
			     freeNode(tmp);
			}
		 }
     }
}

void HashTraversal()
{
     printf("Print Hash:\n");
     int i=0;
     for(i=0; i<D_HASHSIZE; i++)
     {
         if(hashtab[i] !=NULL )
         {
            printf("%d---",i);
            Node * tmp;
            for(tmp=hashtab[i]; tmp!=NULL; tmp=tmp->next)
            {
                 printf("%s ==> %s;",tmp->key,tmp->value);
            }
            printf("\n");
         }
     }
}   

static unsigned int _Hash(char *key)
{
    return _ELFHash(key)%D_HASHSIZE;
}

// ELF Hash Function
static unsigned int _ELFHash(char *str)
{
       unsigned int hash = 0;
       unsigned int x = 0;

       while (*str)
      {
           hash = (hash << 4) + (*str++);//hash左移4位，当前字符ASCII存入hash
           if ((x = hash & 0xF0000000L) != 0)
           {//如果最高的四位不为0，则说明字符多余7个，如果不处理，再加第九个字符时，第一个字符会被移出，因此要有如下处理。

           //该处理，如果对于字符串(a-z 或者A-Z)就会仅仅影响5-8位，否则会影响5-31位，因为C语言使用的算数移位
           hash ^= (x >> 24);  
		   /**
				因为x除了5-8位为!0其余全部为0
				hash ^ 0X000000F0 ===>hash中除了5-8位其余位均无影响,
										相当于位与1操作（&0X111111) 效果是一样的
										其余的值原封保留
										
				
		   */
		   
           //清空28-31位。
           hash &= ~x;	
		   /*
				:(x虽然右移了24位但是x的值并未改变)
				x取反后除了高四位其余都为1
				hash与运算的结果还是5-8位置
		   */
           }
       }

      //返回一个符号位为0的数，即丢弃最高位，以免函数外产生影响。(我们可以考虑，如果只有字符，符号位不可能为负)
     return (hash & 0x7FFFFFFF);

}

static void freeNode(Node * item)
{
   free(item->key);
   free(item->value);
   free(item);
}
 
 
int test2(void)
{
//  Node *nodePtr;

    HashInit();

    HashInsert("tom", "18");
    HashInsert("jerry", "20");
    HashInsert("spike", "22");

    HashTraversal();

    printf("\nupdate spike age:\n");
    HashInsert("spike", "0");
    HashTraversal();


    printf("\nremove tom:\n");
    HashRemove("tom");
    HashTraversal();

    return 0;


}

 
int main(void)
{
	 test2(void);
	 return 0; 
}